#include <iostream>
#include <vector>

struct ListNode
{
    int val = 0;
    ListNode *next = nullptr;
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr)
            return nullptr;

        return _sortList(head, nullptr);
    }

    ListNode* _sortList(ListNode* begin, ListNode* end)
    {
        //如果只有一个元素的话，断开链表返回这个元素
        if(begin->next == end)
        {
            begin->next = nullptr;
            return begin;
        }

        //找到中间节点
        ListNode* slow = begin;
        ListNode* fast = begin;
        while(fast != end)
        {
            slow = slow->next;
            fast = fast->next;
            if(fast != end)
                fast = fast->next;
        }

        //递归
        ListNode* mid_node = slow;
        ListNode* left_list = _sortList(begin, mid_node);
        ListNode* right_list = _sortList(mid_node, end);

        //合并两个有序链表并返回该链表
        return merge(left_list, right_list);
    }

    //合并两个有序链表
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        ListNode* cur1 = head1, *cur2 = head2;
        //确定头节点
        ListNode* head = cur1->val <= cur2->val ? cur1 : cur2;
        if(head == cur1)
            cur1 = cur1->next;
        if(head == cur2)
            cur2 = cur2->next;
        
        //开始合并
        ListNode* tmp = head;
        while(cur1 != nullptr && cur2 != nullptr)
        {
            if(cur1->val <= cur2->val)
            {
                tmp->next = cur1;
                tmp = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tmp->next = cur2;
                tmp = cur2;
                cur2 = cur2->next;
            }
        }
        //将未合并完毕的放入到后面
        if(cur1 != nullptr)
            tmp->next = cur1;
        if(cur2 != nullptr)
            tmp->next = cur2;
        
        return head;
    }
};